Nekega dne je Ančka vsa obupana prosila brata Jureta, naj ji napiše program za domačo nalogo. Ta bi moral rekurzivno izračunati vsoto prvih n naravnih števil. A ker se je Juretu mudilo na vsakodnevni žur, je moral zelo hiteti in je zato v programu naredil nekaj napak. Jih najdeš?
def vsota( n) :
if n > 0 :
return 1
else :
return vsota(n-1)def vsota( n) : if n <= 0 : return 0 else : return n + vsota(n-1)
Jure je napisal kodo, ki s pomočjo rekurzije izračuna
vsoto 1 + 1/2 + 1/3 + ... + 1/n. Žal mu je med sprehodom
list s kodo padel v sneg in se je nekaj kode izbrisalo. Dopolni jo!
def vsotaRec(n) :
'''Izračun 1 + 1/2 + ... + 1 / n
n je zagotovo naravno število
'''
if _______________ : # ustavitveni pogoj
return ___________
return ___________ + vsotaRec(_______) # rekurzivni klicdef vsotaRec(n) : '''Izračun 1 + 1/2 + ... + 1 / n n je zagotovo naravno število ''' if n == 1 : # ustavitveni pogoj return 1 return 1 / n + vsotaRec(n - 1) # rekurzivni klic
Dana je rekurzivna funkcija `izpisObratniR', ki izpiše števila v obratnem vrstnem redu.
def izpisObratniR(stevec) :
if stevec <= 0 :
return ""
else :
niz = "" + str(stevec) + ", " + izpisObratniR(stevec - 1)
return nizKot vidiš, se na koncu izpiše odvečna vejica. Potrebujemo metodo, ki bi še vedno uporabljala rekurzijo, a ne bi izpisala dodatne vejice
def izpisObratniR(stevec): '''Znebimo se odvečne , ''' if stevec <= 0: return "" if stevec == 1: return "1" niz = "" + str(stevec) + ", " + izpisObratniR(stevec - 1) return niz
Sedaj na osnovi te metode sestavi izpisR(stevec), ki bo vrnila števila v
"pravem" vrstnem redu. Še vedno pa uporabi rekurzijo in pazi, da
ne bo odvečnih vejic!
def izpisR(stevec): if stevec <= 0 : return "" if stevec == 1 : return "1" niz = izpisR(stevec - 1) + ', ' + str(stevec) return niz
Sestavite rekurzivno funkcijo steviloEnk(n), ki prešteje, koliko je
enk v dvojiškem zapisu nenegativnega celega števila n.
Primer: Število 52 je v dvojiškem zapisu enako 110100, torej so v njem tri enke. Če se ne spomniš postopka, si oglej ta posnetek
def steviloEnk(n): '''Koliko enk je v dvojiškem zapisu števila n''' if n < 2: return n return n % 2 + steviloEnk(n // 2)
Janezek mora za kazen prebarvati vrtno ograjo. Ta je sestavljena iz deščic širine 1 dm, ki so položene tesno skupaj ena ob drugi. Deščice so različnih višin, saj je ograjo izdelal Janezek sam iz odvečnih kosov, vsaka deščica pa se dotika tal, ki so ravna. Ograja izgleda nekako takole:
+-+
+-+ | | +-+
| | +-+-+ | | |
+-+ | | | | +-+-+ +-+
| | +-+ | | | | | | |
| | | | | | | | | | |
---------------------------Janezek pozna višino vsake deščice, zato lahko ograjo opiše s seznamom, ki za vsako deščico vsebuje po eno število (višina v dm):
[2, 4, 1, 3, 3, 5, 2, 2, 4, 2]Janezek ima čopič, ki je širok ravno 1 dm. Ograjo bo barval z navpičnimi in vodoravnimi potegi čopiča (nikoli ne vleče čopiča diagonalno). To počne tako, da se ob vsakem trenutku vse ščetine čopiča dotikajo ograje. Ponovno lahko potegne čopič tudi preko že pobarvanega dela ograje.
Janezek bi rad prebarval ograjo z minimalnim številom potez, da bi
lahko čimprej odšel na obisk k Pepci. Sestavite funkcijo
stevilo_potez(ograja), ki dobi seznam z opisom ograje in vrne
minimalno število potez. Zgled:
>>> stevilo_potez([2, 2, 1, 2, 1])
3
>>> stevilo_potez([2, 2])
2
>>> stevilo_potez([5])
1def stevilo_potez(ograja): '''Koliko potez je potrebnih za prebarvanje ograje ''' if len(ograja) == 0: # ni ograje return 0 if len(ograja) == 1: # eno deščico prebarvamo naenkrat return 1 min_visina = min(ograja) poteze = min_visina # Vodoravne poteze. # sedaj barvamno od leve proti desni p = [] # kaj je ostalo še za prebarvati na levi strani for i in range(len(ograja)): # pogledamo vse deščice if ograja[i] != min_visina: # deščica je višja, kot najnižja p.append(ograja[i] - min_visina) # pobarvati moramo še njen zgornji del else: # pobarvati moram vse levo, kar še nismo pobarvali prej poteze += stevilo_potez(p) # Barvanje "podograje". p = [] # levo je sedaj pobarvano vse poteze += stevilo_potez(p) # ko smo na koncu, pobarvamo še preostale višje dele return min(poteze, len(ograja)) # Druga možnost so same navpične poteze.
Pri črkovalnikih (npr. Besana), optičnem prepoznavanju znakov in še marsikje nam zelo prav pride, če znamo za dva niza ugotoviti, kako podobna sta si, oziroma kakšna je razdalja med njima. Poznamo več različnih razdalj med nizi: Hammingovo, Damerau-Levenshteinovo, razdaljo največjega skupnega podniza ...
V MaFiRa Wikiju piše, da
Levenshteinova razdalja (angl. Levenshtein distance ali edit distance) med
dvema nizoma predstavlja minimalno število operacij, ki jih potrebujemo za
preoblikovanje enega niza v drugega. Operacije so izbris, vstavljanje in
zamenjava znakov. Dolžini nizov sta lahko poljubni.
Niz
Npr. 'banana' se od 'ananas' razlikuje za 2, ker potrebujemo vsaj dve operaciji, da iz banane naredimo ananas. Npr.
'banana' --(zbrišemo b)-> 'anana' --(vstavimo s)-> 'ananas'
Verjetno se ne boste čudili, da je razdalja med pojmoma 'matematika' in 'fizika' kar 7 ;-)
Sestavite funkcijo levenshteinovaRazdalja(a, b), ki kot argumenta prejme
niza a in b. Funkcija naj vrne urejevalniško razdaljo med a in b.
>>> levenshteinovaRazdalja('banana', 'ananas')
2
>>> levenshteinovaRazdalja('potop', 'pokol')
2
>>> levenshteinovaRazdalja('matematika', 'fizika')
7Nalogo rešite z rekurzijo, torej brez uporabe zanke for oziroma while.
Namig: niza si predstavljajte kot xA in yB. In potem preverite, katera od treh
možnost za predelavo bo dala minimalno vrednost ... Pri tem ne pozabite še na možnost, da
je x == y
def levenshteinovaRazdalja(a, b): ''' Vrne Levenshteinovo razdaljo med nizoma a in b''' if a == "": # v prazen niz moramo vstaviti vse znake iz b return len(b) if b == "": # pobrisati moramo vse znake iz a return len(a) if a[0] == b[0]: # če bomo znak pustili in spreminjali preostanek dodatek = 0 else: dodatek = 1 # tu bomo znaka zamenjali # lahko znak iz a pobrišemo in preostanek a spremenimo v b # ali a spremenimo v cel b razen prvega in na začetek vstavimo prvi znak b-ja # ali pa preostanek a spremenimo v preostanek b in upoštevamo še morebitno spremembo prvega znaka return min(1 + levenshteinovaRazdalja(a[1:], b), levenshteinovaRazdalja(a, b[1:]) + 1, dodatek + levenshteinovaRazdalja(a[1:], b[1:]))
Oznake idej se nanašajo na prosojnice permutacije v spletni učilnici FMF za predmet Programiranje 1 v š.l. 15/16
Če hočemo narediti permutacijo iz 0 elementov, vrnemo tako kot itertools [[]]
Na osnovi ideje 1 smo zgradili osnutek metode permutacijeV1(seznam).
Dopolni ga do delujočega!
def permutacijeV1(seznam):
'''Vrne seznam seznamov, kjer posamezni seznam predstavlja
permutacijo elementov iz seznama '''
... manjka
prviDel = seznam[:-1]
zadnji = seznam[-1]
permPrej = permutacijeV1(prviDel)
# vstavi zadnji na vsa možna mesta
rez = []
for
koncnaPer = permPrej z vstavljenim zadnjim
rez.append(koncnaPer)
...
return sorted(rez)def permutacijeV1(seznam): '''Vrne seznam seznamov, kjer posamezni seznam predstavlj permutacijo elementov iz seznama ''' if seznam == []: # ni elementov, le prazna permutacija return [[]] if len(seznam) == 1: # en sam element - ena permutacija! return [[seznam[0]]] prviDel = seznam[:-1] zadnji = seznam[-1] permPrej = permutacijeV1(prviDel) rez = [] for posameznaP in permPrej: '''Iz te perm. naredimo len(seznam) novih ''' for i in range(len(seznam)): novaP = posameznaP[:] novaP.insert(i, zadnji) rez.append(novaP) return sorted(rez)
Na osnovi ideje 2 smo zgradili osnutek metode permutacijeV2(seznam).
Dopolni ga do delujočega!
def permutacijeV2(seznam):
'''Vrne seznam seznamov, kjer posamezni seznam predstavlja
permutacijo elementov iz seznama '''
... manjka
vse = []
for ind, elt in enumerate(seznam):
# zgradimo vse permutacije iz ostalih
vsePerm = permutacijeV2(seznam[:ind] + seznam[ind + 1:] )
# in sedaj permutacijam dodamo na začetek element elt
...
...
return sorted(vse)def permutacijeV2(seznam): '''Vrne seznam seznamov, kjer posamezni seznam predstavlja permutacijo elementov iz seznama ''' if seznam == []: # ni elementov, le prazna permutacija return [[]] vse = [] for ind, elt in enumerate(seznam): # zgradimo vse permutacije iz ostalih vsePerm = permutacijeV2(seznam[:ind] + seznam[ind + 1:] ) # in sedaj permutacijam dodamo na začetek element elt for perm in vsePerm: vse.append([elt] + perm) return sorted(vse)
Na osnovi ideje 3 smo zgradili osnutek metode permutacijeV3(seznam).
Dopolni ga do delujočega!
def permutacijeV3(seznam, doSedaj = []):
'''Vrne seznam vseh možnih permutacij iz elementov v elementi,
ki imajo začetek enak permutaciji, ki so predstava doSedaj'''
# Če smo že na koncu
return [doSedaj]
vse = []
for elt in seznam:
# če elt še lahko dodamo v doslej sestavljeno permutacijo
# generiramo vse permutacije z začetkom doSedaj + [elt]
# dodamo vsem
return sorted(vse)def permutacijeV3(seznam, doSedaj = []): '''Vrne seznam vseh možnih permutacij iz elementov v elementi, ki imajo začetek enak permutaciji, ki so predstava doSedaj''' if seznam == []: # ni elementov, le prazna permutacija return [[]] if len(seznam) == len(doSedaj):# Če smo že na koncu return [doSedaj] vse = [] for elt in seznam: if not elt in doSedaj: # če elt še lahko dodamo v doslej sestavljeno permutacijo permut = permutacijeV3(seznam, doSedaj + [elt]) # generiramo vse permutacije z začetkom doSedaj + [elt] vse += permut #dodamo vsem return sorted(vse)
Na osnovi ideje 4 smo zgradili osnutek metode permutacijeV4(seznam).
Dopolni ga do delujočega!
import itertools
def permutacijeV4(seznam):
'''Vrne seznam seznamov, kjer posamezni seznam predstavlja
permutacijo elementov iz seznama '''
# uporabimo itertools
# pazimo, ker ta vrne seznam naborov!
return sorted(vse)import itertools def permutacijeV4(seznam): '''Vrne seznam seznamov, kjer posamezni seznam predstavlja permutacijo elementov iz seznama ''' # uporabimo itertools permu = itertools.permutations(seznam) vse = list(map(list, permu)) # pazimo, ker ta vrne seznam naborov! return sorted(vse)